package 代码coding题OR模拟题;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
/**
 * 如果 只是 求    一个  满足 要求的 数组的 话 那么 直接 模拟 就行
 * 进阶：
 * 	求出所有 满足  的 缺失 数组的 话  这得 使用 回溯 了 对吧 
 * 写一下  这种情况 吧  
 * 
 * @author I adore you
 *
 */
public class leetcode2028找出缺失的数据 {
	
	public static int [] solution(int rolls[],int mean,int n) {
		int m = rolls.length;
		int sumM = 0;
		for(int i : rolls) {
			sumM += i;
		}
		int sumN = (m + n) *mean -sumM;
		if(mean > 6 || sumN > n * 6 || sumN < n) {
			return new int[] {};
		}
		int ans [] = new int [n];
		int value = sumN / n;
		int mod = sumN % n;
		/**
		 * 这里 有一些 其他的 情况 
		 * 其实 写 这些 题 主要 就是 是否 能够 把握 住 所有的 情况 
		 * 是否 考虑   全面 
		 */
		for(int i = 0;i < n - 1;i++) {
			if(mod > 0) {
				ans[i] =  value+1;
//				  多出来的 一些 数 直接 匀到 前面的  数中 这也是一种 不错的 思想     这种 只适合 求出 一种合适的情况即可 
				mod--;
			}
			else
				ans[i] = value;
		}
		ans[n-1] = value + mod;
		return ans;
	}
	public static List<List<Integer>> advanceSolution(int rolls[],int mean,int n) {
		List<List<Integer>> ans = new ArrayList<>();
		int m = rolls.length;
		int sumM = 0;
		for(int i : rolls) {
			sumM += i;
		}
		int sumN = (m + n) *mean -sumM;
		if(mean > 6 || sumN > n * 6 || sumN < n) {
//			return new int[] {};
			return ans;
		}
		Deque<Integer> path = new ArrayDeque<>();
		process(n,ans,path,sumN,1);
		return ans;
	}
	/**
	 * 进阶 版本  直接 求出 所有的  满足  条件的 组合
	 * 这样的话  就不要 返回 集合 了 直接 返回 list  list 集合 存储的  是每一种组合
	 * 这他妈 又 引出了 一个 问题 就是  [1,1,1,6] 和 [6,1,1,1] 和 [1,6,1,1,1]这其实 是 同一种 情况   
	 * 这里 等复习 完 回溯 问题 再来 解决在这个 
	 *  **                      下面 已解决   ***
	 * @param rolls
	 * @param mean
	 * @param n
	 * @return
	 */
	public static void process(int n,List<List<Integer>> ans,Deque<Integer> path,int rest) {
		if(rest ==0 && path.size()==n) {
			ans.add(new ArrayList<>(path));
			return ;
		}
//		  这里 还得 写 一些 过滤 条件   比如rest < 0  或者path.size >n 这种情况 
//		  这些 情况  也可以写在    下面的  for循环 中吧
		for(int i = 1;i <= 6 && path.size() < n && rest - i >= 0; i++ ) {
//			path.add(i);
			path.addLast(i);
			process(n,ans,path,rest - i);
			path.removeLast();
		}
	}
	/**
	 * 原来 这种  组合 求和  重复 是 打这 来的 的
	 * 还是 有了 新的 理解的 
	 * 注意 这是 组合 无序的  如果 是 排列
	 * 那么 下面 这三种 都是 不同的 结果   注意 组合 无序 排列 有序 就行了 
	 * [1,1,1,6] 和 [6,1,1,1] 和 [1,6,1,1,1]
	 * 解决 这种 问题 就是  不要 让 i 每次 都从 1 开始 就行 了 所以 
	 * 这个 时候 就体现 出来了   这种                   startIndex  的 重要性了 
	 * 	if(rest == 0 && path.size() == n) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		注意上 面 这个 if 条件 是  是 rest 和 size & 的关系 像这种 你必须 要写 过滤的 条件的
		
		可以这样写   在 上面 这个 if的前面 或者 后面  但这样 并不是 最优做法 
		if( rest < 0 ||  path.size() > n){
		          return;
		}
		
		这样 是 最优 做法  因为 这样的 话  连  for 循环的 递归 它都进不去   
		这样 效率 更高 
	 * int i = index; i <= 6 && rest - i >= 0 && path.size() <= n
	 * i = index 这是  组合  去重 对吧  **  组合   去重***
	 * rest - i 剪枝
	 * 这个 剪枝 是 需要 集合 数据 是有序 的  但该题 是 1~n 本就有序 
	 * 排序 还是 不要忘了的 
	 * path.size 也是 剪枝 
	 */
	static int a = 0;
	public static void process(int n,List<List<Integer>> ans,Deque<Integer> path,int rest,int index) {
		a++;
		if(rest == 0 && path.size() == n) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		for(int i = index; i <= 6 && rest - i >= 0 && path.size() <= n; i++) {
			 path.addLast(i);
			 process(n,ans,path,rest - i,i);
			 path.removeLast();
		}
		
	}
	public static void main(String []args) {
//		int []rolls = {4,5,6,2,3,6,5,4,6,4,5,1,6,3,1,4,5,5,3,2,3,5,3,2,1,5,4,3,5,1,5}; 
//		int mean = 4, n = 40;
//		int []rolls = {3,2,4,3};
//		int mean = 4, n = 2;
		int []rolls = {1,5,6};
		int mean = 3, n = 4;
		String str  = Arrays.toString(solution(rolls,mean,n));
		System.out.println(str);
		System.out.println(advanceSolution(rolls,mean,n));
		System.out.println(a);
		
	}
}
